Coding Theory 编码理论

基础

Shannon’s Theorem 香农理论

考虑一个binary symmetric channel，其中每一位传输错误的概率为$p$。记$q := 1-p$。

假设$C$是一个长度为$n$,包含$M$个词（$x_1,…,x_M$）的code。设$P_i$为$x_i$被错误解码的概率，

$P_C := \frac{1}{M}\sum^M_{i=1}P_i$

以及

$P^*(M,n,p) := \underset{\text{all possible codes }C}{\text{min}} P_C$

Definition:

The channel capacity $C(p)$ of a binary symmetric channel is defined as:

$\begin{align*}C(p) &:= 1 + p \, \text{log}_2(p)+ q \,\text{log}_2(p) \\&=1 + p \, \text{log}_2(p)+ (1-p) \, \text{log}_2(1-p)\end{align*}$

Theorem (Shannon’s Theorem 香农定理):

Let$C(p)$ be the channel capacity. If $0 < R < C(p)$ and $M_n := 2^{\lfloor Rn \rfloor}$, then

$\underset{n \to \infty}{\text{lim}}P^*(M_n,n,p) = 0.$

首先R其实表示的是目前编码的传输效率，因为当传输n位的信息时，其中只有$\text{log}_2(M)$位是真的有效信息。

所以可以这样理解Shannon’s Theorem 香农定理：

对于每个频道（Channel）来说，$C(p)$是其传输效率（R）的上限。

注意到，当$p=0.5$时，$C(p) = 1 + \text{log}_2(0.5) = 1-1 = 0$ 。也就是说，当传输时每一位的准确率都是纯随机的时候，不存在任何编码使得我们可以正确地传输数据。

Bounds/界限

Singleton Bound

Theorem:

Let $q$ be a prime power and $k \leq n$ be positive integers. Let $C$ be an $[n,k]_q$ linear code. Then,

$d_H(C) \leq n-k+1.$

MDS Code

Definition:

A code that achieves the Singleton bound is called a maximum distance separable (MDS) code.

Hamming bound

Theorem (Hamming bound):

Let $q$ be a prime power and $k \leq n$ be positive integers. Let $C$ be an $[n,k]_q$ linear code with $d_H(C) \geq d$ and let $t = \lfloor \frac{d-1}{2} \rfloor$. Then,

$|C| \leq \frac{q^n}{V_H(t,n,q)}$

Equivalently,

$\begin{align*}q^k &\leq \frac{q^n}{V_H(t,n,q)}\\\Leftrightarrow q^{n-k} &\geq V_H(t,n,q)\\\Leftrightarrow q^{n-k} &\geq \sum^t_{i=0}\binom{n}{i}(q-1)^i\\\end{align*}$

Perfect Code

Definition:

Let $q$ be a prime power and $k \leq n$ be positive integers. An $[n,k,d]_q$ linear code $C$ with

$q^{n-k} = V_H(\lfloor \frac{d-1}{2} \rfloor,n,q)$

,i.e. achieves the Hamming bound, is called a perfect code

Definition （Hamming Code）:

Let $q$ be a prime power and $r \geq 2$ be a positive integer. Let $n = \frac{q^r-1}{q-1}$ and $H$ be the $r \times n$ matrix having as columns all vectors in $\mathbb{F}^r_q$ up to non-zero scalar multiples. Then $\mathcal{C} = \text{ker}(H^T)$ is called Hamming code.

Lemma:

Let $q$ be a prime power and $r \geq 2$ be a positive integer and set $n = \frac{q^r-1}{q-1}$. The $[n,n-r]_q$ Hamming code has $d_H(\mathcal{C}) = 3$ and is perfect.

Gilbert-Varshamov Bound

Let $A(d,n,q)$ be the largest size of any code (also non-linear) in $\mathbb{F}^n_q$ with minimum distance at least $d$.

Theorem (Hamming bound):

Let $q$ be a prime power and $n,d$ be positive integers. Then,

$A(d,n,q) \geq \frac{q^n}{V_H(d-1,n,q)}$

Plotkin Bound

Theorem (Plotkin Bound):

Let $q$ be a prime power and $k \leq n$ be positive integers. Let $C$ be an $[n,k]_q$ non-degenerate linear code. Then,

$d_H(C) \leq \frac{|C|}{|C|-1}n\frac{q-1}{q}.$

The simplex code achieves this Plotkin Bound.